The present invention relates to an encryption and decryption technique of information used in the field such as information communication networks, traffic systems, banking facilities, medical services, distribution industries and the like, and more particularly to a circuit and a system for modulo exponentiation arithmetic and an arithmetic method of performing modulo exponentiation arithmetic for realizing the encryption and decryption of the information.
With the development of the information communication technique, ensuring the security on the information network (to prevent stealing and destruction of data) is being regarded as important. For this purpose, the encryption and decryption technique of information is being used not only in the information communication field but also in the fields such as traffic systems, banking facilities, medical service, distribution industries and the like. Accordingly, the encryption and decryption technique of this kind is required to be able to realize the high-degree security by a simple principle.
In order to facilitate understanding of the technique of this kind, encryption and decryption of information is now described in brief.
In cryptography, the "asymmetric cryptograph algorithm" is excellent qualitatively. In the asymmetric cryptograph algorithm, the encryption key and the decryption key are different from each other and one key cannot be calculated easily from the other key.
The representatives of the asymmetric cryptograph algorithm involve the RSA cryptograph, the Elgamal cryptograph, the Rabin cryptograph and the Williams cryptograph using the modulo exponentiation arithmetic. In the application of the cryptograph algorithm, there is the "digital signature" system and there is a tendency to standardization thereof in the present. The representatives of the digital signature systems to be standardized involve the RSA signature method, the Elgamal signature method, the Schnorr signature method and the DSA (Digital Signature Algorithm) method, all of which use the modulo exponentiation arithmetic of a long bit length. Accordingly, it is indispensable to develop an arithmetic unit capable of completing the modulo exponentiation arithmetic having a long bit length in a short time in order to realize the digital signature system.
The RSA cryptograph, the Elgamal cryptograph, the Rabin cryptograph and the Williams cryptograph basically use the modulo exponentiation arithmetic form represented by the following equation (1). The equation (1) means that a remainder of X.sup.Y divided by N is calculated. Further, in the equation (1), X represents a plaintext to be encrypted (decrypted), and Y and N represent keys for encryption (decryption). EQU X.sup.Y modN (1)
The modulo exponentiation arithmetic can be used to perform the encryption and the decryption of information easily and make it difficult to cryptanalize the keys by lengthening the bit length of operands of X, Y and N.
However, when the bit length of the operand is made long, it takes a long time to perform the modulo exponentiation arithmetic. The point is how the modulo exponentiation arithmetic having a long bit length of the operand is completed in a short time.
The actual encryption and decryption using the modulo exponentiation arithmetic and the usage thereof are now described by taking the RSA cryptograph as an example.
(1) SUMMARY OF ENCRYPTION AND DECRYPTION OF THE RSA CRYPTOGRAPH
For the encryption, the following equation is used: EQU C=M.sup.e modn (2)
For the decryption, the following equation is used: EQU M=C.sup.d modn (3)
where M represents a plaintext to be encrypted and C represents an encrypted plaintext, that is, a ciphertext. In the equation (2) e and n represent encryption keys and in the equation (3) d and n decryption keys. These keys are previously given the following conditions: EQU n=p.times.q (4) EQU 1==e.times.dmod{LCM(p-1,q-1)} (5)
where "==" means that the left side and the right side of the equation are similar and LCM means the least common multiple. Further, p and q are relatively prime integers. In addition, the keys e and n are public keys and d, n and q are secret keys.
The above equations (4) and (5) both define conditions of numerical values of the modulo exponentiation arithmetic in the encryption algorithm. The equation (4) defines that n is a product of large prime numbers p and q which are prime to each other. The prime numbers p and q are both odd numbers and accordingly the product n must be naturally an odd number. Further, the equation (5) shows that a remainder of a product c.times.d of c and d divided by the least common multiple of values obtained by subtracting 1 from p and q shown in the equation (4) is 1.
On the basis of the equations (4) and (5), the plaintext M is encrypted by means of the equation (2) and the encrypted plaintext M (ciphertext C) is decrypted by means of the equation (3).
(2) EXAMPLE OF ENCRYPTION AND DECRYPTION
Referring to FIG. 2, description is made to a processing method performed by a transmitting person A and a receiving person B in the case where "the transmitting person A encrypts the plaintext M into the ciphertext C to transmit it and the receiving person B decrypts the ciphertext C into the plaintext M." (with the digital signature) as a definite example.
THE PROCESS PERFORMED BY THE TRANSMITTING PERSON A:
The plaintext MA prepared by the transmitting person A is encrypted by means of the transmitting person's own secret key dA to prepare a signature text CA (signature). EQU CA==MA.sup.dA modnA (6)
The public key eB of the person B is used to prepare an encrypted signature text cA (encryption). EQU cA==CA.sup.eB modnB (7)
The cA is transmitted to the person B.
THE PROCESS PERFORMED BY THE RECEIVING PERSON B:
The encrypted signature text cA received by the person B is decrypted by means of the receiving person's own secret key dB (decryption). EQU cA.sup.dB modnB==(CA.sup.eB modnB).sup.dB modnB (8)
When CA.sup.eB =X, the equation (8) can be transformed to: EQU (CA.sup.eB modnB).sup.dB modnB=(XmodnB).sup.dB modnB (9)
In the equation (9), when XmodnB=Y, that is, when a remainder of X divided by nB is Y and a quotient thereof is k, the equation can be expressed by: EQU X=k.times.nB+Y EQU Y=X-k.times.nB (10)
Accordingly, when the equation (10) is substituted for the corresponding portion in the right side of the equation (9), the equation (9) is expressed by: EQU (XmodnB).sup.dB modnB EQU =Y.sup.dB modnB EQU =(X-k.times.nB).sup.dB modnB (11)
When (X-k.times.nB).sup.dB of the equation (11) is expanded by using constants ai (i=1, 2, . . . ), the (X-k.times.nB)dB can be expressed by: EQU (X-k.times.nB).sup.dB EQU =(X.sup.dB -a1.times.X.sup.dB-1 .times.nB+a2.times.X.sup.dB-2 .times.nB.sup.2- . . . -ai.times.nB.sup.dB) (12)
When the equation (12) is substituted for the corresponding portion of the equation (11), ##EQU1## The second and subsequent terms of this equation can be all divided by nB and can be hence deleted. Accordingly, this equation is expressed by: EQU =X.sup.dB modnB (13)
CA.sup.eB =X is assumed above and accordingly when X is returned to CA.sup.eB, the equation is obtained as follows: EQU =(CA.sup.eB).sup.dB modnB (14)
When the above process is summarized, the above equation is as follows: ##EQU2##
Since the eB and dB satisfy the equation (5), the eB and dB are expressed by the following equation by using a certain integer h. EQU eB.times.dB=h(pB-1)+1
When the Fermat's small theorem that the equation: X.sup.p-1 modp=1 is effected for the prime number p and any integer X which is prime to p is used, the above equation is expressed by: ##EQU3## Since the above equation is satisfied even if CA is a multiple of pB, CA.sup.eB.times.dB -CA for all CA can be divided by pB. Similarly, CA.sup.eB.times.dB -CA can be divided by qB. Since pB and qB are different prime numbers, CA.sup.eB.times.dB -CA CA can be divided by nB=pB.times.qB. Accordingly, the following equation is effected. EQU cA.sup.dB modnB==CA.sup.eB.times.dB modnB(=CA)
The public key eA of the transmitting person is used to prepare the plaintext MA (authentication of signature). ##EQU4## When calculation is made in the same manner as the above decryption process, the following equation is derived. EQU =MA
As described above, values of e, d and n are determined under condition of the equations (4) and (5) and the modulo exponentiation arithmetic form represented by the equation (1) is used basically, so that plaintext can be encrypted and the encrypted plaintext can be decrypted.
For example, when n=15, e=3, p=5, q=3 and d=11 (n=p.times.q=5.times.3=15, e.times.dmod(p-1).times.(q-1)=3.times.11mod4.times.2=33mod8=1) and plaintext M=13, encryption and decryption are made as follows, respectively: EQU C=M.sup.e modn=13.sup.3 mod15=2197mod15=7 EQU M=C.sup.d modn=7.sup.11 mod15=1977326743mod15=13
It is confirmed that the plaintext M=13 is decrypted.
(3) MODULO EXPONENTIATION ARITHMETIC METHOD
The modulo exponentiation arithmetic method used in encryption and decryption is now described.
The modulo exponentiation arithmetic of A=M.sup.e modN is executed by using the iterative square and multiplication method shown in the following flow 1 with the binary expansion of the integer e being e=e.sup.k-1 . . . e.sup.1 e.sup.0. ##EQU5##
The iterative square and multiplication method is expressed by a flow chart of FIG. 3.
First, an initial value 1 is loaded into a register A. The value stored in the register A is multiplied by itself to calculate A.times.A and the product A.times.A is divided by N to obtain a remainder. The remainder is stored in a register a. Then, the value stored in the register a is loaded into the register A. At this time, if the exponent e is equal to 1, the value stored in the register A is multiplied by the plaintext M and the product thereof is divided by N to obtain a remainder, which is stored in the register a. Then, the contents of the register a is stored into the register A again. If the exponent e is equal to 0, the above calculation is not performed and the value stored in the register A remains as it is without any operation. The above calculation is repeatedly performed from the most significant bit to the least significant bit of e, so that the value stored finally into the register A is a solution of the modulo exponentiation arithmetic to be calculated.
As described above, the foundation of the arithmetic is the multiplication and division (modular arithmetic) as shown by the equations (16) and (17). The multiplication performs A.times.A or A.times.M for the value of A having 1 as its initial value and the division performs modN for the value obtained by each multiplication. A pair of arithmetic operations of the multiplication and the division (A.times.AmodN or A.times.MmodN) are repeated in accordance with bit values of "e". That is, the multiplication and the division are performed in accordance with the contents of bits from the most significant bit to the least significant bit of "e".
The foregoing has described the modulo exponentiation arithmetic which can obtain a solution by repeating the basic remainder arithmetic or modular arithmetic, while the number of times of the repetition is several hundreds to thousands at most and accordingly the repetitive operation can be treated even by the software process. However, the modular arithmetic itself requires a large-scale arithmetic circuit and a complicated processing procedure in order to perform the division and accordingly it is desired to improve the modular arithmetic.